package com.mgq.algorithm.dp;

/**
 * 最小硬币数
 * 给一个array,里面表示硬币的面值(正数).给一个数m,返回最小的硬币个数
 * 例如 [2,7,3,5,3] m是10
 * 7,3 最小硬币个数是2
 */
public class MinCoins {

    public static int minCoins(int[] array, int aim) {
        return f(array, 0, aim);
    }

    /**
     * @param array 硬币数组
     * @param index 表示当前到达的索引index
     * @param rest  剩余的金额
     * @return 返回值表示 当前剩余的金额,还需要几次才能够凑够给定的值
     * 返回最小硬币个数
     */
    public static int f(int[] array, int index, int rest) {
        //剩余金额为负数时,返回-1,表示不合规
        if (rest < 0) {
            return -1;
        }
        //表示已经达到了总面值,还需要0次就满足条件
        if (rest == 0) {
            return 0;
        }
        //rest>0,并且下标到达了最后,说明没有硬币了,也没有达到所需的金额
        if (index == array.length) {
            return -1;
        }
        //rest >0
        //包含当前index和不包含当前index
        int p1 = f(array, index + 1, rest);
        int p2Next = f(array, index + 1, rest - array[index]);
        //正常应该是 return  Math.min(p1, p2Next); 由于有-1,所以需要单独考虑
        // return  Math.min(p1, p2Next);
        if (p1 == -1 && p2Next == -1) {
            return -1;

        } else {
            if (p1 == -1) {
                //+1表示要
                return p2Next + 1;
            }
            if (p2Next == -1) {
                return p1;
            }
            return Math.min(p1, p2Next + 1);
        }
    }

    /**
     * dp版本
     *
     * @param array
     * @param aim
     * @return
     */
    public static int minCoins2(int[] array, int aim) {
        //变量是index和rest
        //index是从0->N, rest -> aim 0-10 (rest有可能是负数,索引下标没法表示负数)
        //index会到达 array.length,所以长度+1
        int[][] dp = new int[array.length + 1][aim + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < aim + 1; j++) {
                //-1表示一种状态,因此我们使用-2
                //0也是一个有用的值,0表示还需要0枚硬币就可以组成给定的总金额数
                dp[i][j] = -2;
            }
        }
        return f2(array, 0, aim, dp);
    }

    /**
     * dp 版本
     *
     * @param array
     * @param index
     * @param rest
     * @return
     */
    public static int f2(int[] array, int index, int rest, int[][] dp) {
        //剩余金额为负数时,返回-1,表示不合规. dp没法缓存rest<0的情况.所以不管
        if (rest < 0) {
            return -1;
        }
        if (dp[index][rest] != -2) {
            return dp[index][rest];
        }
        //表示已经达到了总面值,还需要0次就满足条件
        if (rest == 0) {
            dp[index][rest] = 0;
            return dp[index][rest];
        }
        //rest>0,并且下标到达了最后,说明没有硬币了,也没有达到所需的金额
        if (index == array.length) {
            dp[index][rest] = -1;
            return dp[index][rest];
        }
        //rest >0
        //包含当前index和不包含当前index
        int p1 = f2(array, index + 1, rest, dp);
        int p2Next = f2(array, index + 1, rest - array[index], dp);
        //正常应该是 return  Math.min(p1, p2Next); 由于有-1,所以需要单独考虑
        // return  Math.min(p1, p2Next);
        if (p1 == -1 && p2Next == -1) {
            dp[index][rest] = -1;
            return dp[index][rest];
        } else {
            if (p1 == -1) {
                //+1表示要
                dp[index][rest] = p2Next + 1;
                return dp[index][rest];
            }
            if (p2Next == -1) {
                dp[index][rest] = p1;
                return dp[index][rest];
            }
            dp[index][rest] = Math.min(p1, p2Next + 1);
            return dp[index][rest];
        }
    }

    /**
     * 使用严格表结构的方式
     * @param array
     * @param aim
     * @return
     */
    public static int minCoins3(int[] array, int aim) {
        int N = array.length;
        int[][] dp = new int[N+ 1][aim + 1];
        //先填初始位置
        for (int row = 0; row < dp.length; row++) {
            dp[row][0]=0;
        }
        //从1出发, 修改最后一行
        for (int col = 1; col < aim + 1; col++) {
            dp[N][col]=-1;
        }
        //表格依赖的位置是下一个index和 rest-array[index]的值
        //所以表格从下往上计算
        //最后一行已经计算, 因此index从N-1开始
        for (int index = N-1; index >=0; index--) {
            //第0列已经填充了0,所以列从1开始
            for (int rest = 1; rest < aim + 1; rest++) {
                int p1 = dp[index + 1][rest];
//                int p2Next = f(array, index + 1, rest - array[index]);
                // rest - array[index] 可能会越界,因此需要处理越界的情况
                int p2Next=-1;
                if (rest - array[index] >= 0) {
                     p2Next=dp[index+1][rest-array[index]];
                }
                //正常应该是 return  Math.min(p1, p2Next); 由于有-1,所以需要单独考虑
                // return  Math.min(p1, p2Next);
                if (p1 == -1 && p2Next == -1) {
                    dp[index][rest] = -1;
                } else {
                    if (p1 == -1) {
                        //+1表示要
                        dp[index][rest]= p2Next + 1;
                    } else if (p2Next == -1) {
                        dp[index][rest] = p1;
                    } else {
                        dp[index][rest]= Math.min(p1, p2Next + 1);
                    }
                }
            }
        }
        return dp[0][aim];
    }

    /**
     * 使用严格表结构的方式
     * 1.分析可变参数的范围
     * 2.标出需要计算的位置
     * 3.根据base case直接标出不需要计算的位置
     * 4.确定中间位置是怎么依赖的
     * 5.定出严格表,从那些格子到最终位置的顺序
     * 6.copy递归,改成严格表结构形式
     * @param array
     * @param index
     * @param rest
     * @param dp
     * @return
     */
    public static int f3(int[] array, int index, int rest, int[][] dp) {
        //剩余金额为负数时,返回-1,表示不合规
        if (rest < 0) {
            return -1;
        }
        //表示已经达到了总面值,还需要0次就满足条件
        if (rest == 0) {
            return 0;
        }
        //rest>0,并且下标到达了最后,说明没有硬币了,也没有达到所需的金额
        if (index == array.length) {
            return -1;
        }
        //rest >0
        //包含当前index和不包含当前index
        int p1 = f(array, index + 1, rest);
        int p2Next = f(array, index + 1, rest - array[index]);
        //正常应该是 return  Math.min(p1, p2Next); 由于有-1,所以需要单独考虑
        // return  Math.min(p1, p2Next);
        if (p1 == -1 && p2Next == -1) {
            return -1;

        } else {
            if (p1 == -1) {
                //+1表示要
                return p2Next + 1;
            }
            if (p2Next == -1) {
                return p1;
            }
            return Math.min(p1, p2Next + 1);
        }

    }

    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 100};
        int aim = 5;
        System.out.println(minCoins(array, aim));
        System.out.println(minCoins2(array, aim));
        System.out.println(minCoins3(array, aim));
    }
}
